#ifndef KERNEL_UTILS_TLINKEDLIST_H
#define KERNEL_UTILS_TLINKEDLIST_H

#define TLINKEDLIST_SIGNATURE ('TLLS')
#define TLINKEDLISTNODE_SIGNATURE ('TLLN')

template <class T> class TLinkedList;
template <class T> class TLinkedListNode;

template <class T>
class TLinkedListNode
{
friend class TLinkedList<T>;
public:
	TLinkedListNode( T * item );
	
	inline T * GetItem( void ) const { return fItem; }
	inline TLinkedListNode<T> * GetPrev( void ) const { return fPrev; }
	inline TLinkedListNode<T> * GetNext( void ) const { return fNext; }

private:
#if PARANOID
	uint32 fSignature;
#endif

	T * fItem;
	TLinkedListNode<T> * fPrev;
	TLinkedListNode<T> * fNext;
	bool fShouldDelete;
};


template <class T>
class TLinkedList
{
friend class TLinkedListNode<T>;
public:
	TLinkedList();
	~TLinkedList();
	
	Result Add( T * item );
	Result Add( TLinkedListNode<T> * node );
	Result Insert( TLinkedListNode<T> * node, TLinkedListNode<T> * before );
	Result Remove( T * item );
	Result Remove( TLinkedListNode<T> * node );
	TLinkedListNode<T> * FindNode( T * item );
	
	TLinkedListNode<T> * GetFirst( void ) { return fFirst; }
	TLinkedListNode<T> * GetLast( void ) { return fLast; }
	T * GetFirstItem( void ) { return fFirst != NULL ? fFirst->fItem : NULL; }
	T * GetLastItem( void ) { return fLast != NULL ? fLast->fItem : NULL; }
	uint32 GetCount( void ) { return fCount; }
	
private:
#if PARANOID
	uint32 fSignature;
#endif

	TLinkedListNode<T> * fFirst;
	TLinkedListNode<T> * fLast;
	uint32 fCount;
};


template<class T>
TLinkedListNode<T>::TLinkedListNode( T * item )
{
#if PARANOID
	fSignature = TLINKEDLISTNODE_SIGNATURE;
#endif

	fItem = item;
	fPrev = fNext = NULL;
	fShouldDelete = false;
}
	


template <class T>
TLinkedList<T>::TLinkedList()
{
#if PARANOID
	fSignature = TLINKEDLIST_SIGNATURE;
#endif

	fFirst = fLast = NULL;
	fCount = 0;
}
	

template <class T>
TLinkedList<T>::~TLinkedList()
{
#if PARANOID
	fSignature = 0;
#endif

	fFirst = fLast = NULL;
	fCount = 0;
}


template <class T>
Result TLinkedList<T>::Add( T * item )
{
	PARANOID_ASSERT( fSignature == TLINKEDLIST_SIGNATURE );

	TLinkedListNode<T> * node = new TLinkedListNode<T>( item );

	if( node == NULL )
		return ERROR_OUT_OF_MEMORY;

	node->fShouldDelete = true;
	return Add( node );
}


template <class T>
Result TLinkedList<T>::Add( TLinkedListNode<T> * node )
{
	PARANOID_ASSERT( fSignature == TLINKEDLIST_SIGNATURE );

	if( node == NULL )
		return ERROR_NULL_PARAM;

	PARANOID_ASSERT( node->fSignature == TLINKEDLISTNODE_SIGNATURE );
	
	node->fPrev = fLast;
	node->fNext = NULL;
	
	if( fFirst == NULL )
		fFirst = node;

	if( fLast != NULL )
		fLast->fNext = node;

	fLast = node;
	
	fCount++;
	return RESULT_OK;
}


template <class T>
Result TLinkedList<T>::Insert( TLinkedListNode<T> * node, TLinkedListNode<T> * before )
{
	PARANOID_ASSERT( fSignature == TLINKEDLIST_SIGNATURE );

	if( node == NULL )
		return ERROR_NULL_PARAM;
	
	PARANOID_ASSERT( node->fSignature == TLINKEDLISTNODE_SIGNATURE );

	if( before == NULL )
		return Add( node );

	node->fNext = before;

	if( before->fPrev != NULL )
	{
		before->fPrev->fNext = node;
		node->fPrev = before->fPrev;
	}
	else
		node->fPrev = NULL;

	before->fPrev = node;
	
	if( fFirst == NULL || fFirst == before )
		fFirst = node;
	
	if( fLast == NULL )
		fLast = node;
	
	fCount++;
	return RESULT_OK;
}


template <class T>
Result TLinkedList<T>::Remove( T * item )
{
	PARANOID_ASSERT( fSignature == TLINKEDLIST_SIGNATURE );

	TLinkedListNode<T> * node = FindNode( item );
	
	if( node == NULL )
		return ERROR_NULL_PARAM;
	
	PARANOID_ASSERT( node->fSignature == TLINKEDLISTNODE_SIGNATURE );

	Result result = Remove( node );
	
	if( node->fShouldDelete )
		delete node;
	
	return result;
}


template <class T>
Result TLinkedList<T>::Remove( TLinkedListNode<T> * node )
{
	PARANOID_ASSERT( fSignature == TLINKEDLIST_SIGNATURE );

	if( node == NULL )
		return ERROR_NULL_PARAM;
	
	PARANOID_ASSERT( node->fSignature == TLINKEDLISTNODE_SIGNATURE );

	if( node->fPrev != NULL )
		node->fPrev->fNext = node->fNext;
	
	if( node->fNext != NULL )
		node->fNext->fPrev = node->fPrev;
	
	if( fFirst == node )
		fFirst = node->fNext;
	
	if( fLast == node )
		fLast = node->fPrev;

	fCount--;
	return RESULT_OK;
}


template<class T>
TLinkedListNode<T> * TLinkedList<T>::FindNode( T * item )
{
	PARANOID_ASSERT( fSignature == TLINKEDLIST_SIGNATURE );

	if( item == NULL )
		return NULL;

	for( TLinkedListNode<T> * node = fFirst; node != NULL; node = node->fNext )
	{
		if( node->fItem == item )
			return node;
	}
	
	return NULL;
}

#endif // KERNEL_UTILS_TLINKEDLIST_H
